⟸ pàgina anterior ⟸
Exercici 4 (Tasca 7).
(polynomial-time reductions)

Reduccions de temps polinòmic

Considereu la relació \le_m^p entre llenguatges i justifiqueu les respostes a les preguntes següents.

  1. És \le_m^p reflexiva? És a dir, es compleix que A \le_m^p A per a qualsevol llenguatge A?

  2. És \le_m^p simètrica? És a dir, es compleix que si A \le_m^p B, aleshores B \le_m^p A per a qualssevol llenguatges A, B?

  3. És \le_m^p antisimètrica? És a dir, es compleix que A \le_m^p B i B \le_m^p A impliquen A = B per a qualssevol llenguatges A, B?

  4. És \le_m^p transitiva? És a dir, es compleix que A \le_m^p B i B \le_m^p C impliquen A \le_m^p C per a qualssevol llenguatges A, B i C?

Reduccions polinomiques \leq_m^p

Recordeu que, donats dos llenguatges A, B sobre el mateix alfabet \Sigma, diem que A es redueix polinòmicamente a B (s’escriu A\leq_m^p B o A \leq_p B) si existeix una funció total f:\Sigma^*\to\Sigma^* computable en temps polinòmic tal que per a tot w\in \Sigma^*, w\in A si i només si f(w)\in B.

Una propietat útil és el tancament de les classes \mathsf{P}, \mathsf{NP} i \mathsf{coNP} per reduccions polinòmiques, és a dir, donat A\leq_m^p B,

  • si B\in \mathsf{P}, llavors A\in \mathsf{P},
  • si B\in \mathsf{NP}, llavors A\in \mathsf{NP}, i
  • si B\in \mathsf{coNP}, llavors A\in \mathsf{coNP}.

La m en la notació \leq_m^p indica que la funció f no és necessàriament injectiva (és many-one).